package sort;

public class FastSort extends Sort {

    public static void main(String[] args) {
        sort = new FastSort();
        sort.run();
    }

    @Override
    public void sort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int index = spilt(nums, start, end);
        sort(nums, start, index - 1);
        sort(nums, index + 1, end);
    }

    private int spilt(int[] nums, int start, int end) {
        int index = start;
        while (start < end) {
            while (start < end && nums[end] >= nums[index]) {
                end--;
            }
            swap(nums, index, end);
            index = end;

            while (start < end && nums[start] <= nums[index]) {
                start++;
            }
            swap(nums, start, index);
            index = start;
        }
        return index;
    }
}
